package sorted;

import java.util.Arrays;

/**
 * 快速排序
 *
 * @author yujiafan
 * @version 1.0.0
 * @create 2023-02-24
 */
public class QuickSort {
    // <arr[n-1]    arr[n-1]    >arr[n-1]
    public static void splitArr2(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        int N = arr.length;
        int lMost = -1;
        int rMost = N - 1;
        int index = 0;
        while (index < rMost) {
            if (arr[index] < arr[N - 1]) {
                swap(arr, ++lMost, index++);
            } else if (arr[index] > arr[N - 1]) {
                swap(arr, --rMost, index);
            } else {
                index++;
            }
        }
        swap(arr, N - 1, rMost);
    }

    public static void partition(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        process(arr, 0, arr.length - 1);
    }

    public static void process(int[] arr, int L, int R) {
        if (R <= L) {
            return;
        }
        int[] ints = quickSorted(arr, L, R);
        quickSorted(arr, L, ints[0] - 1);
        quickSorted(arr, ints[1] + 1, R);
    }

    public static int[] quickSorted(int[] arr, int L, int R) {
        int lMost = L - 1;
        int rMost = R;
        int index = L;
        while (index < rMost) {
            if (arr[index] < arr[R]) {
                swap(arr, ++lMost, index++);
            } else if (arr[index] > arr[R]) {
                swap(arr, --rMost, index);
            } else {
                index++;
            }
        }
        swap(arr, R, rMost);
        return new int[]{(lMost + 1),rMost};
    }


    public static void main(String[] args) {
        int[] arr = {10, 3, 1, 4, 2, 3, 6, 4, 7, 9, 1, 5, 4};
//        splitArr2(arr);
        partition(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}
